from typing import List


class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        if not obstacleGrid or not obstacleGrid[0]:
            return 0
        dp = [[0 for i in range(len(obstacleGrid[0])+1)]
              for i in range(len(obstacleGrid)+1)]
        dp[0][1] = 1
        for i in range(0, len(obstacleGrid)):
            for j in range(0, len(obstacleGrid[i])):
                if obstacleGrid[i][j] == 1:
                    dp[i+1][j+1] = 0
                else:
                    dp[i+1][j+1] = dp[i][j+1]+dp[i+1][j]
        return dp[-1][-1]


if __name__ == "__main__":
    print(Solution().uniquePathsWithObstacles([
        [0, 0, 0],
        [0, 1, 0],
        [0, 0, 0]
    ]))
